package uba.algo3.tp2.ej1final;

import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.HashMap;

public class PriorityQueueExt<E> extends PriorityQueue {
	/* representacion interna del min-heap, donde se cumple que si i es un nodo, entonces
	 * sus hijos estan en las posiciones 2i+1 y 2i+2 */
	private ArrayList<Ciudad> heap;
	/* indice de cada Ciudad en arrayHeap, para poder obtener desde Maximo.java una ciudad
	 * en tiempo constante */
	private HashMap<Ciudad,Integer> posEnHeap;
	
	public PriorityQueueExt(){ //O(1)
		super();
		heap = new ArrayList<Ciudad>();
		posEnHeap = new HashMap<Ciudad,Integer>();	
	}
	
	public void encolar(Ciudad c){ //O(logN)
		super.add(c); //O(logN)
		heap.add(c); //agrego hoja con la nueva ciudad (O(1))
		posEnHeap.put(c,heap.size()-1); //O(1)
		if (heap.size()>=2) //si el heap estaba vacio, no entro al subir, porq es solo raiz, sin hijos
			subir(heap.size()-1); //subo hoja para reestablecer el invariante del heap (O(logN))
	}
	
	private void subir(int pos){ //O(logN)
		int indiceHija = pos;
		int indicePadre;
		while(indiceHija!=0){ //mientras el indice actual no sea la raiz
			if(indiceHija % 2 != 0) //si es hijo izquierdo
				indicePadre = (indiceHija-1)/2;
			else //si es hijo derecho
				indicePadre = (indiceHija-2)/2;
		  	Ciudad hija = heap.get(indiceHija);
        	Ciudad padre = heap.get(indicePadre);
			if(hija.compareTo(padre) < 0){
				//intercambio posiciones de padre e hijo en posEnHeap
	        	posEnHeap.put(hija,indicePadre);
	        	posEnHeap.put(padre,indiceHija);
				//y tambien en heap
				swap(heap,indiceHija,indicePadre);
				//ahora el indice actual es el indice del padre
				indiceHija = indicePadre;
			}else{
				break; //ya esta restituido el invariante del min-heap
			}
		}
	}
	
	public Ciudad verMax(){ //PreC: !(this.isEmpty())
		return heap.get(0);
	}
	
	public Ciudad getMax(){ //O(logN)
		Ciudad max = (Ciudad) super.poll(); //O(logN)
		Ciudad ultimaHoja = heap.get(heap.size()-1); //O(1)
		posEnHeap.remove(heap.get(0)); //O(1)
		heap.remove(heap.size()-1); //O(1)
		if(heap.size()>0){ //si el heap tenia por lo menos 2 elementos antes de desencolar,
			posEnHeap.put(ultimaHoja, 0); //O(1)
			heap.set(0, ultimaHoja); //O(1)
			bajar(0); //baja el nodo raiz hasta reestablecer el invariante (O(logN))
		}
		return max;
	}
	
	private void bajar(int pos) { //O(logN)
		int n = heap.size();
        int indicehijaIzq, indicehijaDer, indiceMax;
        indicehijaIzq = 2*pos + 1;
        indicehijaDer = 2*pos + 2;
        if (indicehijaDer >= n) {
              if (indicehijaIzq >= n)
                    return;
              else
            	  indiceMax = indicehijaIzq;
        } else {
              if (heap.get(indicehijaIzq).compareTo(heap.get(indicehijaDer)) <= 0) //si ambos son iguales, voy por el nodo izquierdo (asi lo hace el poll de la java api)
            	  indiceMax = indicehijaIzq;
              else
            	  indiceMax = indicehijaDer;
        }
        if (heap.get(pos).compareTo(heap.get(indiceMax)) > 0) {
        	//actualizo en posEnHeap
        	Ciudad padre = heap.get(pos);
        	Ciudad hija = heap.get(indiceMax);
        	posEnHeap.put(padre,indiceMax);
        	posEnHeap.put(hija,pos);
        	//actualizo en heap
        	swap(heap,pos,indiceMax);
            bajar(indiceMax);
        }
    }
	
	public void reubicar(Ciudad c){ //O(logN)
		int pos = posEnHeap.get(c); //O(1)
		subir(pos); //siempre lo voy a subir, nunca bajar, ya que siempre incrementamos prioridad (O(logN))
	}
	
	private void swap(ArrayList<Ciudad> A, int i, int j){ //O(1)
		Ciudad temp = A.get(i);   
        A.set(i,A.get(j));
        A.set(j,temp);
	}
	
	@Override
	public String toString(){ 
		return ""+heap;
		//return ("toStringSuper: " + super.toString() + "   toStringExt: heap: " + heap + " posEnHeap: " + posEnHeap);
	}


}
